The present invention relates to a device and method for searching fixed length data that have a fixed data bit length, and a computer program as well as a computer readable recording medium, and particularly to a device and method for rapidly searching a MAC address in an inter-network relay device, and a computer program as well as a computer readable recording medium.
A database for determining a relay destination used in a conventional inter-network relay device suffers from problems that, because multiple search keys are converted to the same hash value, it requires a long period of time to reconstruct a MAC table, or requires a long period of time to search data required in a MAC address table, compromising an efficient search even with hash functions. To solve these problems, it has been proposed, for example, to use a different table when learning from one when determining an actual relay destination, and provide memory pointers for both of the above hash tables for each entry of a MAC address for example as shown below.
Published Unexamined patent application No. 10-210066Among traditional network switches used for inter-network relay devices, such as L2 (the second layer of the Open System Interconnection (OSI) reference model) switch, L3 (the third layer of the OSI reference model) switch and the like, systems capable of supporting more than tens of thousands of MAC addresses can support a large number of servers and clients. They must, however, search all MAC addresses held in a MAC entry table memory to locate a port corresponding to a MAC address before they can identify the port associated with the MAC address. This would be a significant cause for reducing the performance of a switch for a large network switch means that has more than tens of thousands of MAC addresses.
FIG. 11 shows a structure of a MAC address. A MAC address is used to identify a node connected to a data link, and is specified by IEEE802.3. A MAC address consists of a fixed length datum of 48 bits, and the 3 to 24 bit section of the datum indicates a vender identifier and the 25 to 48 bit section indicates an identifier used within the vender. The vender identifier is an address formally called as an Organizationally Unique Identifier, or OUI, and managed by the IEEE for each vender so that the identifiers will never overlap with each other. The identifier used within the vender is an address managed by the vender for each product so that the identifiers will never overlap with each other.
A destination MAC address that indicates a destination and a source MAC address that indicates a source are attached to the transmitted frames and packets, and are transmitted therewith. A switch means such as L2 switch, L3 switch, and router has a MAC entry table memory to identify a destination port for the frames or packets. The MAC entry table memory is a memory for storing a MAC address table, which is a list showing an association of a MAC address with the corresponding port etc. and retains information on a large number of MAC addresses.
The MAC address table is created based on the source MAC address information separated from the header in a received frame. When the MAC address table is used to search a MAC address, a destination MAC address separated from the header in the received frame is used for this purpose.
To rapidly search any MAC address from more than a hundred thousands of MAC address table memories in a switch means, it is a common practice (1) to provide a cache memory that can temporally retain MAC addresses, and if the received MAC address has already been in the cache memory, the corresponding port address is retrieved from the cache memory and the data are transferred only to the port, and (2) if the destination MAC of interest has not yet retained in the above cache memory, the data need to be transferred to all ports except the source port by so-called broadcasting.
In the case of the above (1), it is difficult to store more than a hundred thousands of MAC addresses in a cache memory of a practical size, and when a switch means handles communications exceeding the amount that the cache can accommodate, more frequent broadcasts as described above (2) may occur.
Broadcasting increases the load on the associated networks because it is processed so that packets are simultaneously placed onto every associated network. As a result, broadcasting may cause all networks to fall into a state as if they are temporally stopped, leading to the decreased throughput of the associated switch means.
An example using a cache as described above (1) uses Content Addressable Memory, or CAM. Although using CAM enables to rapidly search a MAC address (also referred to as a fast search hereinafter), CAM does not allow for the manufacturing of a CAM because of its construction and cannot store a MAC address table with more than tens of thousands of entries.
There may be some possible search methods when general memories are used to rapidly search a MAC address (a fast search) without using CAM. For example, (3) when more than a hundred thousands of MAC addresses are sorted in a way adapted to the search method, the quick search using a binary search, for example, can be used to search a MAC address within 18 times of memory accesses if the number of entries of MAC addresses is 128k.
To use such an algorithm, however, the MAC address table must always be arranged to facilitate a search operation. Some network hosts such as mobile products, however, will not always make a connection at the same place. The correlation between some MAC addresses and port addresses of some switches/routers, therefore, may continuously vary over time and may repetitively be added and removed. Data in the MAC entry table memory, therefore, must regularly be rearranged in response to the addition and removal of data in the MAC entry table memory. The rearrangement requires a long period of time, typically between few milliseconds and several ten milliseconds, for entries more than a hundred thousands, and this substantially makes it impractical to use general memories for searching a MAC address.
To efficiently store inconsecutive data such as MAC addresses, the following processes are involved: it is a common practice (4) to associate a hash value generated by a hash function with a memory address in a memory pointer table so that entry data such as MAC addresses can be substantially dispersed by the hash method, correlating only one entry datum with each memory address in the MAC address table.
It is, however, impossible to uniformly disperse memory addresses of all entry data because of inexistence of a perfect hash function. If different MAC addresses, or entry data for a function, coincide with each other in their hash values, multiple data are correlated with the same memory address in a MAC entry table memory storing a MAC address table. This requires a process of selecting one of the aforementioned multiple data during a search operation, and also requires that store addresses should be changed in response to the addition and removal of data in constructing the MAC entry table, presenting problems that data should be rearranged, or an amount of memory several times larger than that of data expected to be stored should be provided to accommodate the maximum amount of data in consideration of duplication of memory addresses.